/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 1201. 丑数 III
 * <a href="https://leetcode.cn/problems/ugly-number-iii/description/">...</a>
 * User: DELL
 * Date: 2023-11-06
 * Time: 22:26
 */
public class Solution {
    /**
     * 解题思路: (容斥原理 + 二分查找)
     * 特别说明:丑数是指只包含因子2，3，5的数
     * 而本题中规定的丑数为可以被 a 或 b 或 c 整除的正整数
     * 因此本题的丑数不是正规的丑数，而是基于本题定义的，二者不同，不要混淆
     * 且题目中没有规定 a/b/c 为质数
     * 本题题解较为复杂，这里不做陈述，详情见如下 leetcode 官方题解
     * <a href="https://leetcode.cn/problems/ugly-number-iii/solutions/2003797/javac-rong-chi-yuan-li-er-fen-cha-zhao-b-bf69/">...</a>
     *
     * @return
     */
    public int nthUglyNumber(int n, int a, int b, int c) {
        int left = 1;
        int right = Integer.MAX_VALUE - 1;
        int mid;
        while (left < right) {
            // 注意这里如果写成 (left+right)/2 将会越界
            mid = (right - left) / 2 + left;
            if (check(n, a, b, c, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int n, int a, int b, int c, int num) {
        if (num <= 0) {
            return false;
        }
        long ab = lcm(a, b);
        long ac = lcm(a, c);
        long bc = lcm(b, c);
        long abc = lcm(lcm(a, b), c);
        long temp = (long) num / a + num / b + num / c
                - num / ab - num / ac - num / bc
                + num / abc;
        return temp >= n;
    }

    private long gcd(long a, long b) {
        long temp = a % b;
        while (temp != 0) {
            a = b;
            b = temp;
            temp = a % b;
        }
        return b;
    }

    private long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

}
